11269. Лемурьи вечеринки – базовая

 

В подчинении у короля лемуров Джулиана есть ровно 2 * k лемуров по 2 лемура каждого из k видов. Джулиан обожает вечеринки, поэтому каждый вечер он устраивает тусовку, однако в VIP-зоне, к сожалению, хватает мест только для него и еще n других лемуров.

Поскольку Джулиан не любит устраивать “одинаковые” вечеринки, то ему каждый день приходится выбирать кого звать в VIP-зону, чтобы наборы лемуров из VIP-зоны никогда не повторялись. Два лемура одного вида считаются неразличимыми. Наборы считаются одинаковыми, если они совпадают как мультимножества видов лемуров.

Помогите Джулиану определить, сколько дней он сможет проводить различные вечеринки. Так как ответ может быть большим, выведите его по модулю 1000000007.

 

Вход. В одной строке даны два целых числа k и n (1 ≤ k ≤ 500 000, 0 ≤ n ≤ 2 * k) – количество видов лемуров и количество мест в VIP-зоне.

 

Выход. Выведите одно число – ответ на задачу по модулю 1000000007.

 

Пример входа 1

Пример выхода 1

3 3

7

 

 

Пример входа 2

Пример выхода 2

4 3

16

 

 

РЕШЕНИЕ

комбинаторика

 

Анализ алгоритма

На n мест некоторые виды будут представлены двумя лемурами, а некоторые одним. Пусть выбранными окажутся i пар лемуров (i видов представлены двумя лемурами), этот выбор можно совершить  способами. После этого в VIP зоне останется n – 2i мест. Такое количество лемуров можно выбрать из k – i оставшихся видов (по одному лемуру из каждого из k – i оставшихся видов). Такой выбор можно сделать  способами. Поскольку i может принимать любое значение от 0 до k, получаем ответ

 

Пример

Рассмотрим второй тест, где имеется k = 4 пары лемуров и n = 3 места в VIP-зоне. По формуле получим:

 =  +   = 4 + 12 = 16

Выпишем только ненулевые слагаемые.  считаем равным нулю, если выполняется одно из трех неравенств: k < 0, n < 0 или k > n.

Обозначим лемуров буквами {a, a, b, b, c, c, d, d}. Одинаковым буквам соответствуют лемуры одного типа. Слагаемому  = 4 соответствует факт, что никакие два лемура одного вида не являются выбранными, каждый из трех выбранных лемуров принадлежит разным видам. Возможными 4 выборками являются:

 

Рассмотрим слагаемое  = 12. Из одного вида выбраны два лемура (4 варианта). На оставшееся одно место выбирается один лемур из трех оставшихся видов. Возможны 12 вариантов:

 

Очевидно, что два лемура из двух видов на 3 места взять невозможно. Поэтому остальные слагаемые суммы равны нулю.

 

Реализация алгоритма

Объявим константы.

 

#define MAX 1000001

#define MOD 1000000007

 

Объявим массивы: fact содержит факториалы чисел по модулю MOD, factinv содержит числа, обратные факториалам чисел по модулю MOD:

fact[n] = n! mod 1000000007

factinv[n] = n! -1 mod 1000000007

 

typedef long long ll;

ll fact[MAX], factinv[MAX];

 

Функция pow вычисляет степень числа по модулю: xn mod p.

 

ll pow(ll x, ll n, ll p)

{

  if (n == 0) return 1;

  if (n % 2 == 0) return pow((x * x) % p, n / 2, p);

  return (x * pow(x, n - 1, p)) % p;

}

 

Функция inverse находит число, обратное x по простому модулю p. Поскольку число p простое, то по теореме Ферма xp-1 mod p = 1 для всякого 1 ≤ x < p. Равенство можно переписать в виде (x * xp-2) mod p = 1, откуда обратным к x является число xp-2 mod p.

 

ll inverse(ll x, ll p)

{

  return pow(x, p - 2, p);

}

 

Функция Cnk вычисляет биномиальный коэффициент по формуле:

 =

 

ll Cnk(int n, int k)

{

  return ((fact[n] * factinv[k]) % MOD * factinv[n - k]) % MOD;

}

 

Основная часть программы. Читаем входные данные.

 

scanf("%d %d", &k, &n);

 

Заполняем массивы факториалов fact и factinv.

 

fact[0] = 1;

for (i = 1; i < MAX; i++)

  fact[i] = (fact[i - 1] * i) % MOD;

 

factinv[0] = 1;

for (i = 1; i < MAX; i++)

   factinv[i] = inverse(fact[i], MOD);

 

Вычисляем ответ по формуле .  Значение биномиального коэффициента  считаем равным нулю, если выполняется одно из трех неравенств: k < 0, n < 0 или k > n.

 

res = 0;

for (i = 0; i <= k; i++)

{

  if (n - 2 * i < 0 || k - i < 0 || n - 2 * i > k - i) continue;

  res = (res + Cnk(k, i) * Cnk(k - i, n - 2 * i)) % MOD;

}

 

Выводим ответ.

 

printf("%lld\n", res);